package PRQuadtree;

import java.util.LinkedList;
import java.util.Vector;

/**
 * prQuadTree is an implementation of point region quadtree.
 * It's used to store spatial data, hence the data that it stores extends
 * TwoDComparable.
 *
 * @param <T>   -   the type of object the prQuadtree stores.
 */

public class PrQuadTree< T extends TwoDComparable<? super T> > {

    private prQuadNode root;                // pointer to root node, if any
    private prQuadNode flyWeight;
    private long xMin, xMax, yMin, yMax;    // world boundaries
    private boolean inserted;       // an insertion flag
    private boolean deleted;        // a deletion flag
    private String cityFound;       // city's found during removal
    private final int BUCKETSIZE = 3;
    private boolean keyExists = false;


    //Put city coordinate and city name into a single element
    private class Element{
        private T key; // key used in locating element in leaf
        private String value; // value associated with key

        //Construct a new element object
        public Element(T key, String value) {
            this.key = key;
            this.value = value;
        }

        public String getValue() {
            return value.toString();
        }
        public T getKey() {
            return key;
        }
    }

    /**
     * An abstract class representing a point region quad node.
     * It can be either a leaf node or an internal node.
     */
    public class prQuadNode {
        //abstract class
    }
    /**
     * A leaf node is a point region quad node that only contains a key
     * of type T and an element
     */
    private class prQuadLeaf extends prQuadNode {
        private LinkedList<Element> elements; //linkedList implementation storing city records at this leaf

        public prQuadLeaf(){
            elements = new LinkedList<Element>();
        }
        //insert an element into the linkedList
        public boolean insertElement(Element element) {
            boolean aCopy = false;
            LinkedList<Element> tempElements = new LinkedList<Element>();
            int size = elements.size();
            for(int i = 0; i< size; i++) {
                Element e = elements.removeFirst();
                tempElements.add( e );
                //If a copy exists, aCopy = true
                if(e.getKey().equals( element.getKey() )) {
                    aCopy = true;
                }
            }

            //Insert element if it is not already in the list
            if(!aCopy) tempElements.add( element );
            elements = tempElements;
            return !aCopy;
        }

        public int size() {
            return elements.size();
        }
    }
    /**
     * A prQuadInternal is a point region quad node that stores pointers
     * to 4 sub nodes.
     */
    public class prQuadInternal extends prQuadNode {
        prQuadNode nw, ne, sw, se;

        public prQuadInternal(){
            nw=ne=sw=se=flyWeight;
        }

        /**
         * Returns the number of occupied sub nodes.
         *
         * @return  -   number of sub nodes that are not null.
         */
        public int numOcuppiedNodes(){
            int num = 0;
            if(ne != null)
                num++;
            if(nw != null)
                num++;
            if(se != null)
                num++;
            if(sw != null)
                num++;
            return num;
        }
    }

    private class EmptyNode extends prQuadNode {
        private String debug = "E";
    }

    /**
     * It creates a new point region quad tree with the given boundaries.
     *
     * @param xMin  -   left bound
     * @param xMax  -   right bound
     * @param yMin  -   lower bound
     * @param yMax  -   upper bound
     */
    public PrQuadTree(long xMin, long xMax, long yMin, long yMax) {
        flyWeight = new EmptyNode();
        root = flyWeight;
        this.xMin = xMin;
        this.xMax = xMax;
        this.yMin = yMin;
        this.yMax = yMax;
    }


    /** Method that return a boolean value depicting most recent insertion status */

    public boolean getInserted()
    {
        return inserted;
    }

    /**
     * Inserts the given element and returns true if the element was inserted
     * and false otherwise.
     * Inserts the given element if the element does not already exist in the tree
     * and if it's within the required bounds.
     *
     * @param elem  -   element to be added.
     * @return  -   true if insertion was succesful and false otherwise.
     */
    public boolean insert(T key, String c) {
        Element curElement = new Element(key, c);
        root = insert(curElement, root, xMin, xMax, yMin, yMax);
        return inserted;
    }

    /**
     * Deletes the given element if it is in the tree.
     *
     * @param elem  -   element to be deleted
     * @return  -   true if deletion was successful and false otherwise.
     */
    public String delete(T elem) {
        delete(elem, root, xMin, xMax, yMin, yMax);
        return cityFound;
    }

    /**
     * Search for the element given and return it if found.
     *
     * @param elem  -   element being searched for
     * @return  -   Found element if such element is in the tree and null otherwise.
     */
    public T find(T elem) {
        return find(elem, root, xMin, xMax, yMin, yMax);
    }

    /**
     * Search for data points that lie within the region given and return
     * a vector containing those data points.
     *
     * @param xLeft -   left bound of rectangle being searched.
     * @param xRight-   right bound of rectangle being searched.
     * @param yLow  -   lower bound of rectangle being searched.
     * @param yHigh -   upper bound of rectangle being searched.
     * @return  -   a Vector of objects found and null if nothing is found.
     */
    public Vector<T> find(long xLeft, long xRight, long yLow, long yHigh) {
        return find(root, xLeft, xRight, yLow, yHigh, xMin, xMax, yMin, yMax);
    }



    public void clear() {
        root = flyWeight;
    }
    /*
     * Helper method for insertion.
     * Takes the element to be inserted, the node in which the element is
     * to be inserted and bounds of the node.
     */
    private prQuadNode insert( Element e, prQuadNode t, double xMin, double xMax, double yMin, double yMax ){
        inserted = true;    //set the flag to be true
        if (e.getKey() == null){     //if the key is null don't add it
            inserted = false;   // set flag to false and return the node unchanged
            return t;
        }
        else if ( t.equals( flyWeight ) ){  // if the node is null, make a new node with the element and return it.
            prQuadLeaf leaf = new prQuadLeaf();
            leaf.insertElement( e );
            return leaf;
        }
        else if( t.getClass().getName().equals("PRQuadtree.PrQuadTree$prQuadLeaf"))
        {

            prQuadLeaf leaf = (prQuadLeaf) t;
            boolean canInsert = leaf.insertElement( e );
            if(canInsert) {
                //keyExists = false;
            if(leaf.size() == BUCKETSIZE+1) {
                prQuadInternal internal = new prQuadInternal();
                t = (prQuadInternal) internal;
                for(Element elem: leaf.elements) {
                    t= insert( elem, t, xMin, xMax, yMin, yMax  );
                }
            }
            } else {
                //keyExists = true;
                inserted = false;
            }
            return t;
        }
        // if the point is not within the bounds, return the node unchanged and set the flag to false.
        else if (!regionContainsElement(e.getKey(), xMin, xMax, yMin, yMax)){
                inserted = false;
                return t;
        }
        else { // t is an internal node
            //determine which direction the point should go in this region
            // also determine the x and y midpoints of the region
            Direction pointPos = determineRegion(e.getKey(), xMin, xMax, yMin, yMax);
            double xctr = xMin + (xMax - xMin)/2;
            double yctr = yMin + (yMax - yMin)/2;


                // since we're adding a new element and the node we're at already
                // contains an element, initialize a branch node.
                prQuadInternal branch = (prQuadInternal)t;


                // depending on the element's (to be inserted) position recursively
                // pass the element to be added to the corresponding region with the
                // appropriate boundaries specified
                switch (pointPos){
                case NW:    branch.nw = insert(e, branch.nw, xMin, xctr, yMin, yctr); break;
                case NE:    branch.ne = insert(e, branch.ne, xctr, xMax, yMin, yctr); break;
                case SW:    branch.sw = insert(e, branch.sw, xMin, xctr, yctr, yMax); break;
                case SE:    branch.se = insert(e, branch.se, xctr, xMax, yctr, yMax); break;
                default:    branch.nw = insert(e, branch.nw, xMin, xctr, yMin, yctr); break;
                }
                return branch;      // return the modified branch.
            }
    }


    /*
     * Helper method for deletion.
     * Takes the element to be inserted, the node where the element needs to be inserted,
     * and the boundaries of the node as parameters.
     */
    private prQuadNode delete( T key, prQuadNode t, double xMin, double xMax, double yMin, double yMax){
        deleted = true;     // set flag to be initially be true

        //if element is null, set flag to false and return node unchanged.
        if (key == null){
            deleted = false;
            cityFound = " ";
            return t;
        }
        // if the node is null, element is not in there
        else if ( t.equals( flyWeight )){
            deleted = false;    // set to flag to false
            cityFound = " ";
            return t;           // return node unchanged.
        }

        // if the point is not within the bounds given.
        else if (!regionContainsElement(key, xMin, xMax, yMin, yMax)){
            deleted = false;    //set flag to false
            cityFound = " ";
            return t;           // return node unchanged
        }

        //determine which direction the point should go in this region
        // also determine the x and y midpoints of the region
        Direction pointPos = determineRegion(key, xMin, xMax, yMin, yMax);
        double xctr = xMin + (xMax - xMin)/2;
        double yctr = yMin + (yMax - yMin)/2;

        // check if the current node is a leaf node.
        if ( t.getClass().getName().equals("PRQuadtree.PrQuadTree$prQuadLeaf") ) {
            prQuadLeaf tempLeaf = new prQuadLeaf();
            prQuadLeaf leaf = (prQuadLeaf) t;   // cast
            boolean keyFound = false;
            // if leaf contains the element to be deleted
            int size =leaf.size();
            for(int i = 0; i < size; i++) {
                Element tempElement = leaf.elements.removeFirst();
                    if(tempElement.getKey().compare2D(key) == Direction.NONE){
                        keyFound = true;
                        cityFound = tempElement.getValue();
                    } else {
                        tempLeaf.insertElement( tempElement );
                    }
            }

            if (!keyFound) {
                cityFound = " ";
            }

            if (tempLeaf.size() == 0)
            {
                t = flyWeight;
            } else {
                t = tempLeaf;
            }
            return t;
        }
        //if t is an internal node
        else{
            prQuadInternal branch = (prQuadInternal)t;  // cast
            // delete form corresponding node
            // pass the element to the corresponding node with the corresponding
            // boundaries.
            switch (pointPos){
            case NW:    branch.nw = delete(key, branch.nw, xMin, xctr, yMin, yctr);   break;
            case NE:    branch.ne = delete(key, branch.ne, xctr, xMax, yMin, yctr);   break;
            case SW:    branch.sw = delete(key, branch.sw, xMin, xctr, yctr, yMax);   break;
            case SE:    branch.se = delete(key, branch.se, xctr, xMax, yctr, yMax);   break;
            default:    branch.nw = delete(key, branch.nw, xMin, xctr, yMin, yctr);   break;
            }
            // do some cleaning up ... see deleteCleanUp
            return deleteCleanUp(branch);
        }
    }



    /*
     * Helper method for find.
     * Takes the element, the node to be searched and the node bounds as parameters.
     */
    private T find( T key, prQuadNode t, double xMin, double xMax, double yMin, double yMax){
        // check if the element being searched for is null
        if (key == null){
            return null;    // nothing found return null
        }
        // check if the node being searched is null
        else if ( t == null ){
            return null;    // nothing to search .. return null
        }
        // check if the element is out of the allowed bounds
        else if (!regionContainsElement(key, xMin, xMax, yMin, yMax)){
            return null;    // element out of bounds .. return null
        }

        //determine what direction should the point go in this region
        // also determine the x and y midpoints of the region
        Direction pointPos = determineRegion(key, xMin, xMax, yMin, yMax);
        double xctr = xMin + (xMax - xMin)/2;
        double yctr = yMin + (yMax - yMin)/2;

        // check if the current node is a leaf
        if ( t.getClass().getName().equals("PRQuadtree.PrQuadTree$prQuadLeaf") ) {
            prQuadLeaf leaf = (prQuadLeaf) t;   // cast
            // if the element contained in the leaf is equal to the element being
            // searched return that element
            //if(leaf..compare2D(key) == Direction.NONE){
            //    return leaf.key;
           // }
            return null;    // element not found .. return null.
        }
        //if t is an internal node
        else{
            prQuadInternal branch = (prQuadInternal)t;  // cast
            // pass the element to the appropriate node with the appropriate
            // bounds to be searched in there.
            switch (pointPos){
            case NW:    return find(key, branch.nw, xMin, xctr, yMin, yctr);
            case NE:    return find(key, branch.ne, xctr, xMax, yMin, yctr);
            case SW:    return find(key, branch.sw, xMin, xctr, yctr, yMax);
            case SE:    return find(key, branch.se, xctr, xMax, yctr, yMax);
            default:    return find(key, branch.nw, xMin, xctr, yctr, yMax);
            }
        }
    }

    /*
     * Helper function for the region find method.
     * Takes the node being searched, the bounds of the node and the bounds
     * of the rectangle in which the returned points ought to be as parameters.
     */
    private Vector<T> find(prQuadNode t, long xLeft, long xRight, long yLow, long yHigh,
            double xMin, double xMax, double yMin, double yMax) {
        Vector <T> found = new Vector<T>();     // declare a vector to store found elements
        // check if the node is null
        if(t == null)
            return found;   // return the empty vector

        // check if the current node is a leaf
        if(t.getClass().getName().equals("PRQuadtree.PrQuadTree$prQuadLeaf") ){
            prQuadLeaf leaf = (prQuadLeaf) t;       // cast
            //check if the rectangular region given contains the point contained
            // in this leaf
          //  if(regionContainsElement(leaf.key, xLeft, xRight, yLow, yHigh)){
            //    found.add(leaf.key);    // add the element to the vector
            //}
            return found;   // return the updated vector.
        }

        // determine the vertical and horizontal midpoints of region
        long xctr = (long)(xMin + ((xMax - xMin)/2));
        long yctr = (long)(yMin + ((yMax - yMin)/2));

        // node must be an internal node
        prQuadInternal branch = (prQuadInternal) t;     // cast
        // if the region given and this node intersect, go to each sub node
        // and apply the same method
        // append the returned vector from each of the search results
        // to the vector containing found elements.
        if(regionsIntersect(xLeft, xRight, yLow, yHigh, xMin, xMax, yMin, yMax)){
            found = appendVector(found, find(branch.nw, xLeft, xRight,
                    yLow, yHigh, xMin, xctr, yctr, yMax));
            found = appendVector(found, find(branch.ne, xLeft, xRight,
                    yLow, yHigh, xctr, xMax, yctr, yMax));
            found = appendVector(found, find(branch.sw, xLeft, xRight,
                    yLow, yHigh, xMin, xctr, yMin, yctr));
            found = appendVector(found, find(branch.se, xLeft, xRight,
                    yLow, yHigh, xctr, xMax, yMin, yctr));

        }
        return found;       // return modified vector
    }

    /*
     * Determines what part of the region the element belongs to.
     * Takes the element and the bounds of the region as a parameter.
     */
    private Direction determineRegion(T pt, double xMin, double xMax, double yMin, double yMax){
        // Determine vertical and horizontal midpoints of region
        long xctr = (long)(xMin + ((xMax - xMin)/2));
        long yctr = (long)(yMin + ((yMax - yMin)/2));
        // point is on the same y axis of region
        if(pt.getX() == xctr){
            //point is at the center of the region
            if(pt.getY() == yctr)
                return Direction.NONE;
            //point is on the positive y-axis of region
            else if(pt.getY() > yctr)
                return Direction.SE;
            //point is on the negative y-axis of region
            else
                return Direction.NE;
        }
        //point is on the right half of region
        else if(pt.getX() > xctr){
            //point is on the positive x-axis of region
            if(pt.getY() == yctr)
                return Direction.SE;
            //point is in the north east section of region
            else if(pt.getY() > yctr)
                return Direction.SE;
            //point is in the south east section of region
            else
                return Direction.NE;
        }
        //point is on the left half of region
        else{
            //point is in the north west section of region
            if(pt.getY() >= yctr)
                return Direction.SW;
            //point is in the south west section of region
            else
                return Direction.NW;
        }
    }

    /*
     * Checks if the region specified by the first set of bounds intersects
     * with the region specified by the second set of bounds.
     */
    private boolean regionsIntersect(double x1Min, double x1Max, double y1Min, double y1Max,
            double x2Min, double x2Max, double y2Min, double y2Max){
        return (x1Max >= x2Min && x1Min <= x2Max &&  y1Max >= y2Min && y1Min <= y2Max);
    }

    /*
     * Checks if the region specified by the bounds given contains the element given
     */
    private boolean regionContainsElement(T x, double xMin, double xMax, double yMin, double yMax){
        long elemx = x.getX();
        long elemy = x.getY();
        return (elemx >= xMin && elemx <= xMax && elemy >= yMin && elemy <= yMax);
    }

    /*
     * This takes care of special case while deleting.
     * After deleting a subnode of an internal node, this procedure must
     * be executed.
     */
    private prQuadNode deleteCleanUp(prQuadInternal t){
        // check if the internal node has more than exactly one occupied node
        // then return the occupied node if it's a leaf node
        // other wise return the internal node unchanged.
        if(t.numOcuppiedNodes() == 1){
            if(t.nw != null){
                if(t.nw.getClass().getName().equals("PRQuadtree.PrQuadTree$prQuadLeaf") )
                    return t.nw;
            }
            if(t.sw != null){
                if(t.sw.getClass().getName().equals("PRQuadtree.PrQuadTree$prQuadLeaf") )
                    return t.sw;
            }
            if(t.ne != null){
                if(t.ne.getClass().getName().equals("PRQuadtree.PrQuadTree$prQuadLeaf") )
                    return t.ne;
            }
            else{
                if(t.se != null) {
                if(t.se.getClass().getName().equals("PRQuadtree.PrQuadTree$prQuadLeaf") )
                    return t.se;
                }
            }
        }

        return t;   // return internal node unchanged.
    }

    /*
     * Takes two vectors and appends the second vector to the first
     * and returns the resulting vector.
     */
    private Vector<T> appendVector(Vector<T> v1, Vector<T> v2){
        // check if the second vector is null
        if(v2 == null)
            return v1;  // nothing to add to the first so return v1 unchanged.
        // if v2 is not null, append each element in v2 one by one to v1.
        for (T el : v2){
            v1.add(el);
        }
        return v1;      // return the resulting vector.
    }

    /*
     * Provided code
     */

}
